The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet. There are many different scheduling algorithms that achieve one hundred percent throughput within a centrally scheduled, inputs queued switch. Input queued switches typically store packets destined for different destinations in a single queue which can lead to blocking conditions. To avoid this head of queue blocking, many network devices have at each input multiple virtual output queues (VoQs), with one or more queues corresponding to each output of the respective network device. This architecture requires the scheduling of the sending of packets from these multiple VoQs (in contrast to selecting the packet at the head of the single input queue). Prior systems use a combination of virtual output queues (VoQs) and scheduling algorithms based on maximal weight matching. However, the practical implementations of these scheduling algorithms are complex and expensive to implement in hardware at high speed, and is becoming more problematic as line rates continue to increase.
For example, SLIP is an algorithm for scheduling the sending of packets across an N×N switch. In one implementation, the following three steps are performed:    1. Each unmatched input sends a request to every output for which it has a queued cell.    2. If an unmatched output receives any requests, it chooses the one that appears next in a fixed, round-robin schedule starting from the highest selection priority element. The output notifies each input whether or not its request was granted. The pointer to the highest selection priority element of the round-robin schedule is incremented (modulo N) to one location beyond the granted input if and only if the grant is accepted in step 3 of the first iteration. The pointer is not incremented in subsequent iterations.    3. If an input receives a grant, it accepts the one that appears next in a fixed, round-robin schedule starting from the highest selection priority element. The pointer to the highest selection priority element of the round-robin schedule is incremented (modulo N) to one location beyond the accepted output.
I-SLIP is a scheduling algorithm including multiple iterations of the SLIP algorithm to determine the scheduling of packets for each round of sending packets (rather than just one SLIP iteration.)
Each output scheduler decides among the set of ordered, competing requests using a rotating selection priority. When a requesting input is granted and the input accepts that grant, the input will have the lowest selection priority at that output in the next cell time. Also, whatever input has the highest selection priority at an output will continue to be granted during each successive time slot until it is serviced. This ensures that a connection will not be starved: the highest selection priority connection at an output will always be accepted by an input in no more than N cell times.
Moving the pointers not only prevents starvation, it tends to desynchronize the schedulers. Each of the outputs that matched in the previous time slot will have a different highest selection priority input. Thus, they will each grant to different inputs. Consider an example in which two inputs are both requesting the same two outputs. Initially, both outputs may grant to the same input; in that case only one connection will be made in the first iteration.
The successful output will increment its pointer and in the next cell time, the outputs will no longer contend: one will have moved on to grant to another input and the other will grant to the same input as before. This leads to a better match in the first iteration of the next cell time. This is because the output schedulers have become desynchronized (or “slipped”) with respect to each other. This leads to high performance, even for a single iteration of SLIP.
Because of the round-robin movement of the pointers, the algorithm tends to provide a fair allocation of bandwidth among competing connections and to be burst-reducing. The burst-reduction is simplest to understand under high load when all input queues are occupied: the algorithm will visit each competing connection in turn, so that even if a burst of cells for the same output arrives at the input, the burst will be spread out in time if there is competing traffic.
An example implementation is described in Nicholas W. McKeown, “Method and Apparatus for Scheduling Cells in an Input-Queued Switch, U.S. Pat. No. 5,500,858, issued Mar. 19, 1996, which is hereby incorporated by reference. Another example implementation is described in Nicholas W. McKeown, “Combined Unicast and Multicast Scheduling,” U.S. Pat. No. 6,212,182, issued Apr. 3, 2001, which is hereby incorporated by reference.